|
| |
|
|
Online Bin Stretching: Algorithms and Computer Lower Bounds
Böhm, Martin ; Sgall, Jiří (vedoucí práce) ; Durr, Christoph (oponent) ; Kellerer, Hans (oponent)
Online Bin Stretching: algoritmy a strojové dolní odhady Autor: Martin Böhm Abstrakt: Zabýváme se problémem v oblasti semi-online algoritmů, který se nazývá Online Bin Stretching. Můžeme tento problém chápat jako pro- blém opětovného pakování předmětů: cílem algoritmu je zapakovat před- měty různých velikostí do m kontejnerů identické kapacity R > 1. Objekty na vstupu přicházejí jeden po druhém a algoritmus musí přiřadit předmět do kontejneru dříve, než se objeví předmět další. Zvláštnost tohoto konkrétního problému je existence zaručené vlastnosti vstupu, kterou algoritmus zná. Algoritmus totiž už od začátku vstupu má zaručeno, že existuje pakování celého vstupu do m kontejnerů kapacity 1. Naším cílem je navrhnout algoritmy, které pakují jeden objekt po dru- hém a kterým se podaří vstup zapakovat do co nejmenší možné kapacity R. V této dizertační práci představíme několik nových výsledků kolem On- line Bin Stretchingu. Zaprvé, navrhneme algoritmus, který napakuje všechny objekty do m kontejnerů s kapacitou 1,5, a to pro libovolnou počáteční hodnotu m. Zadruhé se soustředíme na podproblém, ve kterém je počet kontejnerů nízký a pevný, například 3. Pro tento model představíme algo- ritmus, který zapakuje vstup do 3 binů s kapacitou 1,375. Nakonec navrhneme a naimplementujeme počítačový program, který bude...
|
|
|
Algoritmické problémy související s průnikovými grafy
Ivánek, Jindřich ; Pergel, Martin (vedoucí práce) ; Rytíř, Pavel (oponent)
V práci studujeme dva problémy pokrytí klikami, které mají zajímavé aplikace při reprezentaci tzv. k -bendovými průnikovými grafy: problém stupně pokrytí hran klikami a problém vrstevnatého pokrytí hran klikami. Zaměřujeme se na složitost těchto problémů a polynomiální algoritmy pro omezené třídy grafů. Hlavními výsledky práce je NP-úplnost problému vrstevnatého pokrytí hran klikami, polynomiální algoritmus pro tento problém na podtřídě grafů bez diamantů a také některé horní odhady pro konkrétní třídy grafů.
|
|
| |
host ::
RSS.